package summary;

import java.util.LinkedList;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/10 17:48
 * https://leetcode-cn.com/problems/sliding-window-maximum/
 */
public class Title239 {

    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 1) {
            return nums;
        }
        int[] result = new int[nums.length - k + 1];
        //模拟单调队列（单调递减）
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            //[i - k + 1, i]
            if (!list.isEmpty() && list.peek() < i - k + 1) {
                list.pop();
            }
            //每次进的元素都要比最后一个元素大(单调递减)
            while (!list.isEmpty() && nums[list.getLast()] < nums[i]) {
                list.pollLast();
            }
            list.offer(i);
            if (i >= k - 1) {
                result[i - k + 1] = nums[list.peek()];
            }
        }
        return result;
    }

    public static int[] maxSlidingWindow1(int[] nums, int k) {
        if (nums.length == 1) {
            return nums;
        }
        int[] result = new int[nums.length - k + 1];
        int count = 0;
        //维持滑动窗口的queue
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            //弹出 [i-k+1, i]
            while (!list.isEmpty() && list.peek() < i - k + 1) {
                list.poll();
            }
            while (!list.isEmpty() && nums[i] > nums[list.getLast()]) {
                list.pollLast();
            }
            list.offer(i);
            if (i >= k - 1) {
                result[count++] = nums[list.peek()];
            }
        }
        return result;
    }













    public int[] maxSlidingWindow2(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        int count = 0;
        //维持滑动窗口
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            //维持滑动窗口[i - k + 1, i]，窗口大小为k
            if (!list.isEmpty() && list.peek() < i - k + 1) {
                list.poll();
            }
            //每次值维护滑动窗口内最大的值
            while (!list.isEmpty() && nums[i] > nums[list.getLast()]) {
                list.pollLast();
            }
            list.offer(i);
            if (i >= k - 1) {
                result[count++] = nums[list.peek()];
            }
        }
        return result;
    }


    public static void main(String[] args) {
        int[] arr = {1,-1};
        int k = 1;
        maxSlidingWindow1(arr, k);
    }
}
